home *** CD-ROM | disk | FTP | other *** search
/ SPACE 2 / SPACE - Library 2 - Volume 1.iso / apps / 93 / applic / qsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-01-15  |  1.3 KB  |  64 lines
  1. /* qsort - quick sort routine */
  2.  
  3. /* translated to C from the 'Software Tools in Pascal' routines
  4.    by Kernighan & Plauger
  5.  */
  6.  
  7. /* qsort - quick sort routine */
  8. qsort(linepos,nlines,cmprec)
  9.   char *linepos[]; int nlines; int (*cmprec)();
  10. {
  11.     qsort1(linepos,0,nlines-1,cmprec);
  12. }
  13.  
  14. /* qsort1 - the real sort routine */
  15. static qsort1(linepos,lo,hi,cmprec)
  16.   char *linepos[]; int lo,hi; int (*cmprec)();
  17. {
  18.     char *pivline;
  19.     int i,j;
  20.  
  21.     /* make sure there's something to sort */
  22.     if (lo >= hi)
  23.     return;
  24.  
  25.     /* initialize */
  26.     i = lo;
  27.     j = hi;
  28.     pivline = linepos[j];
  29.  
  30.     /* partition the set */
  31.     do {
  32.     while (i < j && (*cmprec)(linepos[i],pivline) <= 0)
  33.         i++;
  34.     while (j > i && (*cmprec)(linepos[j],pivline) >= 0)
  35.         j--;
  36.     if (i < j)
  37.         exchange(linepos,i,j);
  38.     } while (i < j);
  39.  
  40.     /* move pivot to i */
  41.     exchange(linepos,i,hi);
  42.  
  43.     /* sort each partition */
  44.     if (i - lo < hi - i) {
  45.     qsort1(linepos,lo,i-1,cmprec);
  46.     qsort1(linepos,i+1,hi,cmprec);
  47.     }
  48.     else {
  49.     qsort1(linepos,i+1,hi,cmprec);
  50.     qsort1(linepos,lo,i-1,cmprec);
  51.     }
  52. }
  53.  
  54. /* exchange - exchange two lines */
  55. static exchange(linepos,l1,l2)
  56.   char *linepos[]; int l1,l2;
  57. {
  58.     char *tmp;
  59.  
  60.     tmp = linepos[l1];
  61.     linepos[l1] = linepos[l2];
  62.     linepos[l2] = tmp;
  63. }
  64.